#include "testlib.h"
#include <string>

using namespace std;
using pii = pair<int, int>;

const int N = 1010;

string s[N];
pii fa[N][N];

pii find(pii a) {
    auto [x, y] = a;
    return fa[x][y] == a ? a : fa[x][y] = find(fa[x][y]);
}

bool merge(pii a, pii b) {
    if(find(a) == find(b)) return false;
    auto [x, y] = find(a);
    fa[x][y] = find(b);
    return true;
}

int main(int argc, char *argv[]) {
    setName("Check if the graph is connected, acyclic and balanced.");
    registerTestlibCmd(argc, argv);

    int n = inf.readInt();
    int tot = n * n;

    for(int i = 0; i < n; i ++) {
        s[i] = ouf.readWord();
        if(s[i].length() != n) {
            quitf(_wa, "Width of row %d invalid.", i + 1);
        }
    }

    bool acyclic = true;
    pii black = pii(-1, -1), white = pii(-1, -1);
    for(int i = 0; i < n; i ++)
        for(int j = 0; j < n; j ++) {
            fa[i][j] = pii(i, j);
            if(s[i][j] != '#' && s[i][j] != '.')
                quitf(_wa, "Unexpected char");
            if(i > 0 && s[i - 1][j] == s[i][j]) {
                acyclic &= merge(pii(i, j), pii(i - 1, j));
            }
            if(j > 0 && s[i][j - 1] == s[i][j]) {
                acyclic &= merge(pii(i, j), pii(i, j - 1));
            }
        }
    if(!acyclic)
        quitf(_wa, "graph not acyclic");
    int cntBlack = 0, cntWhite = 0;
    for(int i = 0; i < n; i ++)
        for(int j = 0; j < n; j ++) {
            if(s[i][j] == '#') {
                if(black == pii(-1, -1))
                    black = find(pii(i, j));
                else if(black != find(pii(i, j)))
                    quitf(_wa, "'#'s are separated");
                cntBlack ++;
            }else if(s[i][j] == '.') {
                if(white == pii(-1, -1))
                    white = find(pii(i, j));
                else if(white != find(pii(i, j)))
                    quitf(_wa, "'.'s are separated");
                cntWhite ++;
            }else{
                quitf(_wa, "Invalid character");
            }
        }
    if(cntBlack + cntWhite != tot || abs(cntBlack - cntWhite) > 1) {
        quitf(_wa, "Not balanced");
    }

    quitf(_ok, "Accepted.");
}
